package com.example.sortingalgorithm;

// 冒泡排序算法
public class BubbleSort {

    /**
     * 冒泡排序算法
     * 举例：
     * 待排序序列：
     * --------------------
     * [3] [5] [4] [2] [1]
     * a0  a1  a2  a3  a4
     * --------------------
     * 序列长度为5，根据冒泡排序算法，需要进行5-1=4趟排序（第1趟排序用于将最大值移动到a4位置，第2趟排序用于将第二大的值移动到a3，以此类推）
     * 第1趟排序：
     * a0和a1比较，若a0 > a1，则交换两个数值的位置
     * a1和a2比较，若a1 > a2，则交换两个数值的位置
     * a2和a3比较，若a2 > a3，则交换两个数值的位置
     * a3和a4比较，若a3 > a4，则交换两个数值的位置 —— 至此，第1趟排序结束，也就是说第1趟排序进行了5-1=4轮两两比较
     * 同样地，通过上面第1趟的排序可以总结出结论：若序列的长度为n，那么第x趟需要进行n-x次两两比较
     * @param array
     * @param <T>
     */
    public static <T extends Comparable> void sort(T[] array){
        T temp = null;

        // i 代表第几趟
        for (int i = 1; i <= array.length - 1; i++){
            // j 控制每一趟比较的次数
            for (int j = 0; j < array.length - i; j++){
                if(largeThan(array[j], array[j+1])){
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
    }

    /**
     * left大于right，则返回true
     * @param left
     * @param right
     * @param <T>
     * @return left大于right，则返回true
     */
    private static <T extends Comparable> boolean largeThan(T left, T right){
        return left.compareTo(right) > 0;
    }
}
